package day07;

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * 输出：false
 */
public class Solution2 {
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int []num : matrix){
            if(binaryLookup(num,target)>=0){
                return true;
            }
        }
        return false;
    }
    public int binaryLookup(int []num,int target){
        int left = 0,right = num.length-1;
        while(left<=right){
            int mid = (right-left)/2 + left;
            if(num[mid]==target){
                return mid;
            }else if(num[mid]>target){
                right = mid-1;
            }else if(num[mid]<target){
                left = mid+1;
            }
        }
        return -1;
    }
}
